package quwei;/*阿里巴巴与四十大盗——背包问题*/
import java.util.Scanner;

class three {
    double w=0;               //每个宝物的重量
    double v=0;               //每个宝物的价值
    double p=0;               //性价比

}


public class Test2_3 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入宝物数量n及毛驴的承载能力m：");
        int n=scanner.nextInt();               //表示n个宝物
        double m=scanner.nextDouble();         //表示毛驴的承载能力
        System.out.println("请输入每个宝物的重量和价值，用空格分开：");

        three[] s=new three[n];                //定义n长的数组存放宝物，数组类型是three型，即数组每位由重量、价格和性价比组成
        for(int i=0;i<n;i++) {
            s[i]=new three();
            s[i].w=scanner.nextDouble();
            s[i].v=scanner.nextDouble();
            s[i].p=s[i].v/s[i].w;
        }
        selectionSort(s);

        double sum=0;                          //表示贪心记录运走宝物的价值之和
        for(int i=0;i<n;i++) {
            if(m>s[i].w) {                     //如果宝物的重量小于毛驴剩下的承载能力
                sum+=s[i].v;                   //宝物价值之和增加
                m-=s[i].w;                     //毛驴承载能力减少
            }
            else {                             //如果宝物的重量大于毛驴剩下的承载能力，则进行部分装载
                sum+=m*s[i].p;                 //价值增加部分重量的价值
                break;
            }
        }

        System.out.println("装入宝物的最大价值Maximum value="+sum);
        scanner.close();
    }   

    public static void selectionSort(three[] array){          //运用选择排序将宝物按照性价比由大到小进行排序
        three temp=new three();
        for(int i=0;i<array.length-1;i++){      
            for(int j=i+1;j<=array.length-1;j++){ 
                 if(array[i].p<array[j].p){          
                    temp = array[i];                          //要将类的所有成员变量进行换位置，因为值是相互对应的
                    array[i] = array[j];
                    array[j] = temp;
                 }
            }
        }
    }
}